package dataStructure.binaryTree;

import java.util.*;

/**
 * 哈夫曼树
 */
public class Huffman extends BinaryTree {
    public static Map<Character, Integer> statistics(char[] charArray) {
        Map<Character, Integer> map = new HashMap<>();
        for (char c : charArray) {
            Character character = c;
            if (map.containsKey(character)) {
                map.put(character, map.get(character) + 1);
            } else {
                map.put(character, 1);
            }
        }
        return map;
    }

    class Node extends TreeNode<String> implements Comparable<Node> {

        public Node(String element) {
            super(element);
        }

        /**
         * 实现小根堆 重新比较函数
         *
         * @param node
         * @return
         */
        @Override
        public int compareTo(Node node) {
            return weight - node.weight;
        }

        public boolean isLeftChild() {
            return parent != null && this == parent.left;
        }

        /**
         * 是否是根结点（没有父节点）
         *
         * @return boolean
         */
        public boolean isRoot() {
            return parent == null;
        }
    }

    //aaaaaaaaaabbbbbaaaaaccccccccddddddfff
    private Huffman buildTree(Map<Character, Integer> statistics, List<Node> leafs) {
        Character[] keys = statistics.keySet().toArray(new Character[0]);
        //根据weight建立小根堆   取出的值为当前堆最小值
        PriorityQueue<Node> queue = new PriorityQueue<>();
        for (Character c : keys) {
            Node node = new Node(String.valueOf(c));
            node.weight = statistics.get(c);
            queue.offer(node);
            leafs.add(node);
        }

        int size = queue.size();
        for (Node node : queue) {
            System.out.println("Node:" + node.element + ", weight:" + node.weight);
        }
        for (int i = 0; i < size - 1; i++) {
            Node node1 = queue.poll();
            Node node2 = queue.poll();
            Node sumNode = new Node(node1.element + node2.element);
            sumNode.weight = node1.weight + node2.weight;

            sumNode.left = node1;
            sumNode.right = node2;

            node1.parent = sumNode;
            node2.parent = sumNode;
            queue.offer(sumNode);
        }
        root = queue.poll();
        return this;
    }

    private static Map<Character, String> buildEncodingInfo(List<Node> leafNodes) {
        Map<Character, String> codewords = new HashMap<>();
        for (Node leafNode : leafNodes) {
            Character character = leafNode.element.charAt(0);
            StringBuilder codeword = new StringBuilder();
            Node currentNode = leafNode;
            do {
                if (currentNode.isLeftChild()) {
                    codeword.insert(0, "0");
                } else {
                    codeword.insert(0, "1");
                }

                currentNode = (Node) currentNode.parent;
            } while (currentNode.parent != null);
            codewords.put(character, codeword.toString());
        }
        return codewords;
    }

    //a(23),c(8),d(6),b(5),f(3)
    //    fb
    //    /\
    //   f  b
    //a(23),c(8),fb(8),d(6)
    //    dfb
    //     /\
    //    d fb
    //      /\
    //     f  b
    //a(23),dfb(14),c(8)
    //    cdfb
    //     / \
    //    c  dfb
    //        /\
    //       d fb
    //         /\
    //        f  b
    //a(23),cdfb(22)
    //    cdfba
    //     / \
    //   cdfb a
    //    / \
    //   c  dfb
    //       /\
    //      d fb
    //        /\
    //       f  b
    //cdfba(45)
    public static void main(String[] args) {
        String testStr = "aaaaaaaaaaaaaaaaaabbbbbaaaaaccccccccddddddfff";
        System.out.println("原文:" + testStr);
        char[] charArray = testStr.toCharArray();
        Map<Character, Integer> statistics = statistics(charArray);
        Huffman huffman = new Huffman();
        List<Node> leafNodes = new ArrayList<>();
        huffman.buildTree(statistics, leafNodes);

        Map<Character, String> encodInfo = buildEncodingInfo(leafNodes);
        System.out.println("字符的Huffman编码:");
        for (Map.Entry<Character, String> entry : encodInfo.entrySet()) {
            System.out.println("Node:" + entry.getKey() + ", Value:" + entry.getValue());
        }

        StringBuilder builder = new StringBuilder();
        for (char c : charArray) {
            Character character = c;
            builder.append(encodInfo.get(character));
        }
        System.out.println("编码后的原文二进制表示:" + builder);
        System.out.println("huffman树前序遍历:");
        huffman.preOrder();
        System.out.println("\nhuffman树中序遍历:");
        huffman.inOrder();
    }
}
